import java.io.*;
import java.util.*;

class Read {
    StringTokenizer st = new StringTokenizer("");
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    public String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }

    public String nextLine() throws IOException {
        return bf.readLine();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }
}


public class Main {

    static Read in = new Read();
    static PrintWriter out = new PrintWriter(System.out);
    public static void main1(String[] args) throws IOException {
        int a = in.nextInt(), b = in.nextInt();
        int max = a * b;
        for (int i = Math.max(a, b);i <= max;i++) {
            if (i % a == 0 && i % b == 0) {
                out.println(i);
                break;
            }
        }
        out.close();
    }

    public int[] FindNumsAppearOnce (int[] nums) {
        int[] ret=new int[2];
        int k=0;
        Map<Integer,Integer> hash=new HashMap<>();
        for(int i=0;i<nums.length;i++) {
            hash.put(nums[i],hash.getOrDefault(nums[i],0)+1);
        }
        for(int i=0;i<nums.length;i++) {
            if(hash.get(nums[i])==1){
                ret[k++]=nums[i];
            }
        }
        if(ret[0]>ret[1]) {
            int a=ret[0];
            ret[0]=ret[1];
            ret[1]=a;
        }
        return ret;
    }

    public static void main2(String[] args) throws IOException {
        int n = in.nextInt(), m = in.nextInt();
        int x = in.nextInt(), y = in.nextInt();
        long[][] dp = new long[n + 2][m + 2];
        dp[0][1] = 1;
        x += 1;
        y += 1;
        for (int i = 1;i <= n + 1;i++) {
            for (int j = 1;j <= m + 1;j++) {
                if (i != x && j != y && Math.abs(i - x) + Math.abs(j - y) == 3 || (i == x && j == y)){
                    dp[i][j] = 0;
                }else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        out.printf("" + dp[n + 1][m + 1]);
        out.close();
    }

    public static void main3(String[] args) throws IOException {
        int n = in.nextInt(), m = in.nextInt();
        char[][] board = new char[n][m];
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0;i < n;i++) {
            String s = in.next();
            for (int j = 0;j < s.length();j++) {
                board[i][j] = s.charAt(j);
            }
        }
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) {
                int s = 0;
                if (board[i - 1][j - 1] == 'l') {
                    s = 4;
                }else if (board[i - 1][j - 1] == 'o') {
                    s = 3;
                }else if (board[i - 1][j - 1] == 'v') {
                    s = 2;
                }else if (board[i - 1][j - 1] == 'e') {
                    s = 1;
                }
                dp[i][j] = Math.max(dp[i - 1][j] + s, dp[i][j - 1] + s);
            }
        }
        out.println(dp[n][m]);
        out.close();
    }

    public static void main5(String[] args) throws IOException{
        long n = in.nextLong();
        long m = in.nextLong();
        long v1 = in.nextLong(), v2 = in.nextLong();
        long ret = 0;
        for (long x = 0;x <= Math.min(n / 2, m);x++) {
            long y = Math.min(n - x * 2, (m - x) / 2);
            ret = Math.max(ret, v1 * x + v2 * y);
        }
        out.println(ret);
        out.close();
    }

    public static void main6(String[] args) throws IOException {
        String s = in.nextLine();
        String[] str = s.split(" ");
        for (int i = str.length - 1;i >= 0;i--) {
            out.print(str[i] + " ");
        }
        out.close();
    }

    public static void main7(String[] args) throws IOException {
        int n = in.nextInt();
        String ss = in.next();
        char[] str = ss.toCharArray();
        long s = 0, h = 0, y = 0;
        for (int i = 0;i < n;i++) {
            if (str[i] == 's') {
                s++;
            }else if (str[i] == 'h') {
                h += s;
            }else if (str[i] == 'y') {
                y += h;
            }
        }
        out.println(y);
        out.close();
    }

    public static void main8(String[] args) throws IOException {
        int t = in.nextInt();
        while (t-- > 0) {
            int n = in.nextInt(), k = in.nextInt();
            String s = in.next();
            int ret = 0;
            for (int i = 0;i < n;i++) {
                if (s.charAt(i) == 'W') {
                    if (i >= 2 && s.charAt(i - 1) == 'W' && s.charAt(i - 2) == 'W') {
                        ret += k;
                    }else {
                        ret++;
                    }
                }else if (s.charAt(i) == 'L') {
                    ret--;
                }
            }
            out.println(ret);
        }
        out.close();
    }

    public static void main9(String[] args) throws IOException {
        String s = in.next();
        int len = in.nextInt();
        int count = 0, max = 0, start = 0;
        int left = 0, right = 0;
        while (right < s.length()) {
            if (s.charAt(right) == 'C' || s.charAt(right) == 'G') {
                count++;
            }
            right++;
            if (count > max) {
                start = left;
                max = count;
                if (count == len) {
                    out.println(s.substring(start, start + len));
                    break;
                }
            }
            if (right - left >= len) {
                if (s.charAt(left) == 'C' || s.charAt(left) == 'G') {
                    count--;
                }
                left++;
            }
        }
        if (right >= s.length()) out.println(s.substring(start, start + len));
        out.close();
    }

    public static void main10(String[] args) throws IOException {
        int n = in.nextInt(), m = in.nextInt();
        int[][] nums = new int[n][m];
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                nums[i][j] = in.nextInt();
            }
        }
        long[][] ret = new long[n][m];
        long[] sum1 = new long[n];
        long[] sum2 = new long[m];
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                sum1[i] += nums[i][j];
            }
        }
        for (int i = 0;i < m;i++) {
            for (int j = 0;j < n;j++) {
                sum2[i] += nums[j][i];
            }
        }
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                ret[i][j] = sum1[i] + sum2[j] - nums[i][j];
                out.print(ret[i][j] + " ");
            }
            out.println();
        }
        out.close();
    }

    public static void main11(String[] args) throws IOException {
        int n = in.nextInt(), k = in.nextInt();
        long[] a = new long[n + 1];
        long[] b = new long[n + 1];
        for (int i = 1;i <= n;i++) {
            a[i] = in.nextLong();
        }
        for (int i = 1;i <= n;i++) {
            b[i] = in.nextLong();
        }
        long hSum = 0, sSum = 0;
        long hMax = 0, sMin = 0;
        int left = 1, right = 1;
        long begin = -1;
        while (right <= n) {
            hSum += a[right];
            sSum += b[right];
            while (right - left + 1 > k) {
                hSum -= a[left];
                sSum -= b[left];
                left++;
            }
            if (right - left + 1 == k) {
                if (hSum > hMax) {
                    hMax = hSum;
                    sMin = sSum;
                    begin = left;
                }else if (hSum == hMax && sSum < sMin) {
                    sMin = sSum;
                    begin = left;
                }
            }
            right++;
        }
        out.println(begin);
        out.close();
    }

    public static void main12(String[] args) throws IOException {
        int n = in.nextInt(), V = in.nextInt();
        int[] value = new int[n];
        int[] cost = new int[n];
        for (int i = 0;i < n;i++) {
            cost[i] = in.nextInt();
            value[i] = in.nextInt();
        }
        int[] dp1 = new int[V + 1];
        int[] dp2 = new int[V + 1];
        Arrays.fill(dp2, Integer.MIN_VALUE);
        dp2[0] = 0;
        for (int i = 0;i < n;i++) {
            for (int j = V;j >= cost[i];j--) {
                dp1[j] = Math.max(dp1[j], dp1[j - cost[i]] + value[i]);
                dp2[j] = Math.max(dp2[j], dp2[j - cost[i]] + value[i]);
            }
        }
        out.println(dp1[V]);
        out.println(dp2[V] < 0 ? 0 : dp2[V]);
        out.close();
    }



    public boolean IsContinuous (int[] numbers) {
        // write code here
        int n = numbers.length;
        int max = 0, min = 14;
        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0;i < n;i++) {
            if (numbers[i] > 0) {
                if (hash.containsKey(numbers[i])) {
                    return false;
                }
                hash.put(numbers[i], i);
                if (numbers[i] > max) max = numbers[i];
                if (numbers[i] < min) min = numbers[i];
            }
        }
        if (max - min >= 5) return false;
        return true;
    }

    public static void main13(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            long n = in.nextLong(), a = in.nextLong();
            List<Integer> nums = new ArrayList<>();
            for (long i = 0;i < n;i++) {
                nums.add(in.nextInt());
            }
            long ret = a;
            for (int i = 0;i < n;i++) {
                if (a >= nums.get(i)) {
                    ret += nums.get(i);
                }else {
                    ret += GCD(a, nums.get(i));
                }
            }
            out.println(ret);
        }
        out.close();
    }

    public static void main(String[] args) throws IOException {
        String s1 = in.next();
        String s2 = in.next();
        int n = s1.length();
        int m = s2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1;i <= n;i++) {
            dp[i][0] = i;
        }
        for (int i = 1;i <= m;i++) {
            dp[0][i] = i;
        }
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        out.println(dp[n][m]);
        out.close();
    }

    public static long GCD (long a, long b) {
        long c = a < b ? a : b;
        for (;c > 0;c--) {
            if (a % c == 0 && b % c == 0) {
                break;
            }
        }
        return c;
    }

    int[] dx = {0, 0, -1, 1};
    int[] dy = {1, -1, 0, 0};
    boolean[][] vis;
    int ret, n, m;
    public int solve (char[][] grid) {
        // write code here
        n = grid.length; m = grid[0].length;
        vis = new boolean[n][m];
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (grid[i][j] == '1' && !vis[i][j]) {
                    dfs(grid, i, j);
                    ret++;
                }
            }
        }
        return ret;
    }
    public void dfs (char[][] grid, int i , int j) {
        vis[i][j] = true;
        for (int k = 0;k < 4;k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && grid[x][y] == '1') {
                dfs(grid, x, y);
            }
        }
    }

    public int MLS (int[] arr) {
        // write code here
        Arrays.sort(arr);
        int ret = 0;
        int len = 1;
        int pre = arr[0];
        for (int i = 1;i < arr.length;i++) {
            if (pre + 1 == arr[i]) {
                len++;
            }else if (pre == arr[i]) {
                continue;
            }else {
                ret = Math.max(len, ret);
                len = 1;
            }
            pre = arr[i];
        }
        ret = Math.max(len, ret);
        return ret;
    }

    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        int[][] dp = new int[n + 1][m + 1];
        int ret = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (nums1[i] == nums2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                }
                ret = Math.max(ret, dp[i + 1][j + 1]);
            }
        }
        return ret;
    }

    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len + 1];
        int ret = Integer.MIN_VALUE;
        for (int i = 0;i < len;i++) {
            dp[i + 1] = Math.max(dp[i] + nums[i], nums[i]);
            ret = Math.max(ret, dp[i + 1]);
        }
        return ret;
    }

    public int getLongestPalindrome (String A) {
        // write code here
        int n  = A.length();
        if (n < 2) return n;
        boolean[][] dp = new boolean[n][n];
        int max = 1;
        for (int i = 1; i < n;i++) {
            dp[i][i] = true;
            for (int j = 0;j < i;j++) {
                if (A.charAt(i) == A.charAt(j) && i - j > 1) {
                    dp[j][i] = dp[j + 1][i - 1];
                }else if (A.charAt(i) == A.charAt(j)) {
                    dp[j][i] = true;
                }else {
                    continue;
                }
                if (dp[j][i] && i - j + 1 > max) {
                    max = i - j + 1;
                }
            }
        }
        return max;
    }

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (p1 != null || p2 != null) {
            if (p1 == p2) {
                return p1;
            }
            p1 = p1 == null ? pHead2 : p1.next;
            p2 = p2 == null ? pHead1 : p2.next;
        }
        return null;
    }

    public ListNode oddEvenList (ListNode head) {
        //如果链表为空，不用重排
        if(head == null)
            return head;
        //even开头指向第二个节点，可能为空
        ListNode even = head.next;
        //odd开头指向第一个节点
        ListNode odd = head;
        //指向even开头
        ListNode evenhead = even;
        while(even != null && even.next != null){
            //odd连接even的后一个，即奇数位
            odd.next = even.next;
            //odd进入后一个奇数位
            odd = odd.next;
            //even连接后一个奇数的后一位，即偶数位
            even.next = odd.next;
            //even进入后一个偶数位
            even = even.next;
        }
        //even整体接在odd后面
        odd.next = evenhead;
        return head;
    }

    public String LCS (String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        if (dp[n][m] == 0) return "-1";
        StringBuilder sb = new StringBuilder();
        while(n > 0&&m > 0) {
            if (s1.charAt(n - 1) == s2.charAt(m - 1)) {
                sb.append(s1.charAt(n - 1));
                n--;
                m--;
            }else{
                if (dp[n - 1][m] > dp[n][m - 1]) {
                    n--;
                }else{
                    m--;
                }
            }
        }
        return sb.reverse().toString();
    }

    public ListNode sortInList (ListNode head) {
        // write code here
        List<Integer> nums = new ArrayList<>();
        while (head != null) {
            nums.add(head.val);
            head = head.next;
        }
        Collections.sort(nums);
        ListNode newHead = new ListNode(0);
        ListNode p = newHead;
        for (int i = 0;i < nums.size();i++) {
            ListNode cur = new ListNode(nums.get(i));
            p.next = cur;
            p = p.next;
        }
        return newHead.next;
    }

    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        ListNode ret = null;
        for(ListNode list:lists) {
            ret = mergeToList(ret, list);
        }
        return ret;
    }
    public ListNode mergeToList (ListNode l1,ListNode l2) {
        if (l1 == null||l2 == null) {
            return l1 != null? l1: l2;
        }
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 != null) cur.next = l1;
        if (l2 != null) cur.next = l2;
        return head.next;
    }

    int[] dx1 = {1,-1,0,0};
    int[] dy1 = {0,0,1,-1};
    int ret1, n1, m1;
    boolean[][] vis1;
    public int solve (int[][] matrix) {
        // write code here
        n1 = matrix.length; m1 = matrix[0].length;
        vis1 = new boolean[n1][m1];
        for (int i = 0;i < n1;i++) {
            for (int j = 0; j < m1;j++) {
                solveRec(i , j, 1, matrix);
            }
        }
        return ret1;
    }
    public void solveRec(int i, int j ,int len, int[][] matrix) {
        for (int k = 0;k < 4;k++) {
            int x = dx1[k] + i;
            int y = dy1[k] + j;
            if (x > 0&&x < n1&&y > 0&&y < m1&&!vis1[x][y]) {
                if (matrix[x][y] <= matrix[i][j] ) {
                    continue;
                }
                vis1[x][y] = true;
                ret1 = Math.max(ret1, len + 1);
                solveRec(x, y, len + 1, matrix);
                vis1[x][y] = false;
            }
        }
    }

    public List<Integer> findSubstring(String ss, String[] tt) {
        List<Integer> ret=new ArrayList<>();
        Map<String,Integer> hash1=new HashMap<>();
        int n=tt.length,m=tt[0].length();
        for(String t:tt){
            hash1.put(t,hash1.getOrDefault(t,0)+1);
        }
        for(int i=0;i<m;i++){
            Map<String,Integer> hash2=new HashMap<>();
            for(int left=i,right=i,count=0;right+m<=ss.length();right+=m){
                String in=ss.substring(right,right+m);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in)<=hash1.getOrDefault(in,0)) count++;
                if(right-left+1>m*n){
                    String out=ss.substring(left,left+m);
                    if(hash2.get(out)<=hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.get(out)-1);
                    left+=m;
                }
                if(count==n) ret.add(left);
            }
        }
        return ret;
    }

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] matrix_new = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix[i][j] = matrix_new[i][j];
            }
        }
    }

    public int maxProfit (int[] prices) {
        // write code here
        int n = prices.length;
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0;i < n;i++) {
            if (prices[i] < min) {
                min = prices[i];
            }
            if (prices[i] - min > max) {
                max = prices[i] - min;
            }
        }
        return max;
    }

    public int maxLength (int[] arr) {
        // write code here
        int n = arr.length;
        if (n < 2) return n;
        int left = 0, right = 0;
        Map<Integer, Integer> hash = new HashMap<>();
        int max = 0;
        for (int i = 0, j = 0;i < n;i++) {
            if (hash.containsKey(arr[i])) {
                j = Math.max(hash.get(arr[i]) + 1, j);
            }
            hash.put(arr[i], i);
            max = Math.max(max, i - j + 1);
        }
        return max;
    }

    public String rearrangestring (String str) {
        // write code here
        int n = str.length();
        char[] s = str.toCharArray();
        int maxCount = 0;
        char maxChar = '0';
        int[] hash = new int[26];
        for (int i = 0; i < n; i++) {
            char ch = s[i];
            if (++hash[ch - 'a'] > maxCount) {
                maxCount = hash[ch - 'a'];
                maxChar = ch;
            }
        }
        if (maxCount > (n + 1) / 2) {
            return "";
        } else {
            char[] ret = new char[n];
            int i = 0;
            while (maxCount > 0) {
                ret[i] = maxChar;
                i += 2;
                maxCount--;
            }
            for (int j = 0; j < 26; j++) {
                if (hash[j] != 0 && (char) (j + 'a') != maxChar) {
                    while (hash[j]-- != 0) {
                        if (i >= n) {
                            i = 1;
                        }
                        ret[i] = (char) (j + 'a');
                        i += 2;
                    }
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(ret[j]);
            }
            return sb.toString();
        }
    }

    public int boredom (ArrayList<Integer> a) {
        // write code here
        int[] hash = new int[10001];
        for (int num : a) {
            hash[num] += num;
        }
        int[][] dp = new int[10001][2];
        for (int i = 1;i < 10001;i++) {
            dp[i][0] = hash[i] + dp[i - 1][1];
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        }
        return Math.max(dp[10000][1], dp[10000][0]);
    }

}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}